题意
求有向图中最大的集合使得集合中的点两两不可到达
求集合的大小，输出1种可行的构造方案，并输出每个点能不能在点集中
题解
第一问：由Diliworth定理，最长反链的长度=最小链覆盖的数量
本来是没有后两问的哪个毒瘤写的spj
第二问：就是求二分图的最大独立集
第三问：把一个点以及和它相连的边和点都删掉，如果最小链覆盖-1，则可以
关于第二问的构造方案
首先不能直接选覆盖链的头或尾来构造，反例显然
这个问题等价于二分图的最大独立集的问题
最大独立集一定等于最小点覆盖的补集：1.它一定是最大的 2.该补集中一定没有连边，如果有的话不满足最小点覆盖
考虑如何求二分图的最小点覆盖：从左边的任何一个未匹配点开始，未匹配边->匹配边…，标记经过的所有点
左侧标记的点和右侧未标记的点就是最小点覆盖，如果i和i+n都在最大独立集里，就加入反链
调试记录
不会构造方案1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
const int maxn = 10005;
const int INF = 0x3f3f3f3f;
using namespace std;
struct E{
int to, nxt, f;
}e[maxn << 1];
int head[maxn], tot = 1;
void addedge(int u, int v, int f){
e[++tot].to = v, e[tot].nxt = head[u], e[tot].f = f;
head[u] = tot;
}
void ins(int u, int v, int f){
addedge(u, v, f);
addedge(v, u, 0);
}
int dep[maxn], now[maxn], T;
bool bfs(){
queue <int> q; while (!q.empty()) q.pop();
q.push(0); memset(dep, 0, sizeof dep); dep[0] = 1;
memcpy(now, head, sizeof now);
while (!q.empty()){
int cur = q.front(); q.pop();
for (int i = head[cur]; i; i = e[i].nxt)
if (!dep[e[i].to] && e[i].f > 0){
dep[e[i].to] = dep[cur] + 1;
q.push(e[i].to);
}
}
return dep[T] > 0;
}
int dfs(int cur, int Max){
if (cur == T) return Max;
int flow = 0;
for (int i = now[cur]; i; i = e[i].nxt){
now[cur] = i;
if (flow == Max) return flow;
if (dep[e[i].to] == dep[cur] + 1 && e[i].f > 0){
int tmp = dfs(e[i].to, min(Max - flow, e[i].f));
e[i].f -= tmp;
e[i ^ 1].f += tmp;
flow += tmp;
}
}
return flow;
}
int maxflow;
void Dinic(){
maxflow = 0;
while (bfs())
maxflow += dfs(0, INF);
}
bool link[105][105];
int n, m;
void Floyd(){
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
link[i][j] |= (link[i][k] & link[k][j]);
for (int i = 1; i <= n; i++) link[i][i] = 0;
}
bool vis[maxn];
void dfs1(int cur){
if (vis[cur]) return;
vis[cur] = 1;
if (cur <= n){
for (int i = head[cur]; i; i = e[i].nxt)
if (e[i].f == 0 && e[i].to != 0) dfs1(e[i].to);
}
if (cur > n){
for (int i = head[cur]; i; i = e[i].nxt)
if (e[i].f == 0 && e[i].to != T) dfs1(e[i].to);
}
} int ex[maxn << 1];
int main(){
scanf("%d%d", &n, &m);
for (int u, v, i = 1; i <= m; i++){
scanf("%d%d", &u, &v);
link[u][v] = 1;
} T = n << 1 | 1; Floyd();
for (int i = 1; i <= n; i++) ins(0, i, 1), ex[i] = tot - 1, ins(i + n, T, 1), ex[i + n] = tot - 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (link[i][j]) ins(i, j + n, 1);
Dinic();
printf("%d\n", n - maxflow);
int tmp = n - maxflow;
for (int i = 1; i <= n; i++)
if (e[ex[i + n]].f != 0) dfs1(i + n);
for (int i = 1; i <= n; i++)
printf("%d", (!vis[i] & vis[i + n]));
puts("");
for (int p = 1; p <= n; p++){
memset(head, 0, sizeof head); tot = 1; int cnt = 0;
for (int i = 1; i <= n; i++)
if (i != p && !link[i][p] && !link[p][i]) ins(0, i, 1), ins(i + n, T, 1), ++cnt;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != p && j != p && link[i][j]) ins(i, j + n, 1);
Dinic();
if (cnt - maxflow == tmp - 1) putchar('1');
else putchar('0');
} putchar('\n');
return 0;
}